class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.save_dic = {}

    def get(self, key: int) -> int:
        try:
            self.save_dic[key] = self.save_dic.pop(key)
            return self.save_dic[key]
        except:
            return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.save_dic:
            if self.save_dic.__len__() >= self.capacity:
                iterer = iter(self.save_dic)
                self.save_dic.pop(next(iterer))
        else:
            self.save_dic.pop(key)
        self.save_dic[key] = value


cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 返回  1
cache.put(3, 3)    # 该操作会使得密钥 2 作废
print(cache.get(2))       # 返回 -1 (未找到)
cache.put(4, 4)    # 该操作会使得密钥 1 作废
print(cache.get(1))       # 返回 -1 (未找到)
print(cache.get(3))       # 返回  3
print(cache.get(4))       # 返回  4